const NIL = {
  key = undefined,
  color = 0,
  lChild = null,
  rChild = null,
}
// 0：红   1：黑   2：双重黑
class Node {
  constructor(key, color = 0, lChild = NIL, rChild = NIL) {
    this.key = key;
    this.color = color;
    this.lChild = lChild;
    this.rChild = rChild;
  }
}

function getNewNode() {
  return new Node(key);
}
function has_red_child(root) {
  return root.lChild.color === 0 || root.rChild.color === 0;
}
function left_roate(root) {
  let newRoot = root.rChild;
  root.rChild = newRoot.lChild;
  newRoot.lChild = root;
  return newRoot;
}
function right_roate(root) {
  let newRoot = root.lChild;
  root.lChild = newRoot.rChild;
  newRoot.rChild = root;
  return newRoot;
}

Node.prototype._insert = function(root, key) {
  if(root.key === undefined) return getNewNode(key);
  if(key === root.key) return root;
  if(key < root.key) {
    root.left = this._insert(root.left, key);
  } else {
    root.right = this._insert(root.right, key);
  }
  return insert_maintrain(root);
}
Node.prototype.insert = function(root, key) {
  root = this._insert(root, key);
  root.color = 1;
  return root;
}

// root为祖父节点
Node.prototype.insert_maintrain = function(root) {
  // 判断是否失衡
  let flag = 0;  // 0: 未失衡   1：L失衡    2：R失衡
  if(root.lChild.color === 0 && has_red_child(root.lChild)) flag = 1; // L
  if(root.rChild.color === 0 && has_red_child(root.rChild)) flag = 2; // R
  if(flag === 0) return root;

  // 插入调整情况一: 父节点和叔节点都为红色
  if(root.lChild.color === 0 && root.rChild.color === 0) {
    root.color = 0;
    root.lChild.color = root.rChild.color = 1;
    return root;
  }

  // 插入调整情况二： LL、LR、RR、RL
    // 旋转
  if(flag === 1) { // L
    if(root.lChild.rChild.color === 0) { //LR
      root.lChild = left_roate(root.lChild);
    }
    root = right_roate(root)
  } else { // R
    if(root.rChild.lChild === 0) { // RL
      root.rChild = right_roate(root.rChild);
    }
    root = left_roate(root);
  }
    // 红色上浮
  root.color = 0;
  root.lChild.color = root.rChild.color = 1;
  return root;
}